package com.labuladong.skill.monotonousStack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

// 单调栈！
// 力扣」第 42、80、739、496、316、901、402、581

// 输入nums[2,1,2,4,3]  返回下一个更大元素数组[4,2,4,-1,-1]
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        if (len1 < 1 || len2 < 1 || len1 > len2) {
            return new int[]{};
        }

        int[] res = new int[len1];

        Stack<Integer> stack = new Stack<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        stack.push(nums2[0]);
        // 右边数字入栈
        for (int j = 1; j < len2; j++) {
            int currNum = nums2[j];
            // 单调栈栈顶元素和当前数组元素作比较

            // 找到下一个更大元素
            while (!stack.isEmpty() && currNum > stack.peek()) {
                map.put(stack.pop(), currNum);
            }

            stack.push(currNum);
        }

        // 栈不为空 这些元素都是找不到下一个更大值的
        while (!stack.isEmpty()) {
            map.put(stack.pop(), -1);
        }

        for (int i = 0; i < len1; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    public int[] template(int[] nums) {
        Stack<Integer> s = new Stack<>();
        int[] res = new int[nums.length];

        for (int i = nums.length - 1; i >= 0; i--) {
            while (!s.isEmpty() && s.peek() < nums[i]) {
                s.pop();
            }

            // s空，意味着后面的元素没有比它更大的
            // s非空 意味着栈顶元素就是该元素的下一个更大值
            res[i] = s.empty() ? -1 : s.peek();

            //
            s.push(nums[i]);
        }

        return res;
    }
}




// 思路 找到右边第一个比它大的值的index
class FindRightFirstBigger {
    public int[] work(int[] arr) {
        int len = arr.length;

        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由大到小 遇上更大的 弹出来  更大的压进去
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                // 意味着i是preIndex的下一个更大值
                int preIndex = stack.pop();

                ans[preIndex] = i;
            }

            // 压入i
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        FindRightFirstBigger f1 = new FindRightFirstBigger();

        System.out.println(Arrays.toString(f1.work(arr)));

    }
}

// 找到右边第一个比它小的元素
class FindRightFirstSmaller {
    public int[] work(int[] arr) {

        int len = arr.length;
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由小到大 遇上更小的  栈全弹出来  更小的压进去
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                // 意味着i是preIndex的下一个更大值
                int preIndex = stack.pop();

                ans[preIndex] = i;
            }

            // 压入i
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        FindRightFirstSmaller f1 = new FindRightFirstSmaller();

        System.out.println(Arrays.toString(f1.work(arr)));

    }
}


// 思路 找到左边第一个比它大的值的index
class FindLeftFirstBigger {
    public int[] work(int[] arr) {
        int len = arr.length;

        Stack<Integer> stack = new Stack<>();  // 这里放元素索引 而不是元素
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由大到小
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                // 矮个子出列
                stack.pop();
            }

            // 这个元素
            ans[i] = stack.empty() ? -1 : stack.peek();

            // 压入i 接收后面身高的审判吧
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        int[] arr01 = new int[]{0, 1, 2, 3, 4, 5, 7, 6};

        FindLeftFirstBigger f1 = new FindLeftFirstBigger();

        System.out.println(Arrays.toString(f1.work(arr)));
        System.out.println(Arrays.toString(f1.work(arr01)));

    }
}


// 思路 找到左边第一个比它小的值的index
class FindLeftFirstSmaller {
    public int[] work(int[] arr) {
        int len = arr.length;

        Stack<Integer> stack = new Stack<>();  // 这里放元素索引 而不是元素
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由小到大
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                // 高个子出列
                stack.pop();
            }

            // 这个元素
            ans[i] = stack.empty() ? -1 : stack.peek();

            // 压入i 接收后面身高的审判吧
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        int[] arr01 = new int[]{0, 1, 2, 3, 4, 5, 7, 6};

        FindLeftFirstSmaller f1 = new FindLeftFirstSmaller();

        System.out.println(Arrays.toString(f1.work(arr)));
        System.out.println(Arrays.toString(f1.work(arr01)));
    }
}
